Multi-station communication systems typically reside in one of two major categories, master controlled systems and master-less systems. General information for both systems is found in the IEEE's Computer Society Press Tutorial entitled "LOCAL COMPUTER NETWORKS", second edition, Kenneth J. Thurber and Harvey A. Freeman, (IEEE CATALOG NO. EHO 1792, copyright 1981). The former category utilizes a central processing unit or other supervisory control which observes and dictates which station has access to the commonly shared data transmission resource; typically the bus interconnecting the various stations. Unlike such systems, the present invention is primarily a master-less communication system.
With respect to master-less communication systems, two general categories exist; namely, contention systems and token pass systems. The former contention systems are unlike the present invention in that they allow multiple stations to contend for access to the bus as the general means for transferring control of the bus from one station to another station. The present invention, although allowing for the possibility of contention when multiple stations simultaneously demand access to the token, generally only uses a contention-less token pass system.
As to contention systems, the joint project developed by Digital Equipment Corporation, Maynard, Mass.; Intel Corporation, Santa Clara, Calif., and Xerox Corporation, Stamford, Conn., known as Ethernet.TM., and as described in U.S. Pat. No. 4,063,200, Metcalfe et al, allows any station connected to the bus to transmit information provided that the bus is clear just prior to and during the transmission. If it detects noise on the bus while transmitting, it is assumed that an interference or collision has occurred between itself and at least one other station attempting to transmit information on the bus at the same time. In order to correct this problem the transmitter section is disabled on each station and a random number generator is used to select an interval of time at the completion of which the next attempt at transmission takes place. At the same time, a counter counts the number of interferences, or collisions, which occur in the attempted transmissions of one data packet and weights the mean of the random number generator accordingly. In this way, the stations attempting to transmit, reattempt to transmit at different times and thus, in time, eliminate the contention between the stations.
The present invention does not utilize such a contention or collision detection system but rather uses the concept of a token which is passed from one station to another such that each station when owning the token has, during that time, the exclusive right to initiate high level message transmissions (sometimes called data link control or "DLC" messages) as well as to request return of high level messages from any other station.
With respect to a token pss communication system, a representative prior art technique is disclosed in U.S. Pat. No. 4,058,681, Imaizumi et al. This reference discloses an information transmission system using a token which is transmitted from one station to the next by use of a command established signal (ELS) and a transfer command signal (SEL). The token is passed from station to station through use of the SEL signal giving the address of the next station which is to have the token. Upon receiving the token, that next station transmits the command establish signal to inform the other stations that it does have command. If the station presently having the token does not transmit an ELS or SEL signal within a predetermined time, another station takes the token by transmitting its own ELS signal. A failure of a station to detect the transfer of the token from itself to the next addressed station within a predetermined time causes the station which originally had the token to retransmit a new SEL signal with a new address so as to transfer the token to a different station.
This reference however does not dislose the concept of an arc of control wherein the present token owner (holder) knows both the station from which it received the token (its "FROM") as well as the station to which it is to next transfer the token (its "TO"). This arc of control in combination with an improved demand window by which the present token owner can transfer the token to a demander not in the token list provides the capability of both patching in and patching out stations to the token list of stations presently passing ownership of the token on a systematic basis. Imaizumi et al also neither discloses nor suggests the concept of automatically changing the handshaking protocol between token passing stations.
While the arc of control and automatic handshaking protocol shifting is disclosed in the '688 application, that application does not disclose or suggest the hashing mechanism, the duplicate address protection system, the improved explicit demander window mechanism, and other improvements of the present invention.
Referring again to Imaizumi et al, it also does not disclose or suggest the binding concept of the present invention wherein stations may have physical connection to the bus and yet never have the possibility of obtaining the token for control of the bus (called "slave" stations). These slave stations are thus only able to respond to other stations which can be token owners. The binding concept allows the communications system to interconnect with relatively low level access stations which would otherwise be incapable of transmitting information on the bus. This binding concept, though disclosed in the '688 application is further improved in the present invention through duplicate address protection of all stations, including slave stations.
Furthermore, the present invention through use of its underlying perceived events and their causal effect through rule interaction to change station states, can be reconfigured to form new and different communications systems having different access mechanism protocols depending upon the particular requirements of a communication network desired by the user.
The present invention provides an improvement over previous token pass communication systems by incorporating several new features. In particular, a initialization procedure now utilizes what is called a "hashing contest" for determining the first station that proceeds with generating a token list (sometimes known as ring building). This technique uses the address of the station and, if required, a random number associated with the station, for determining which station becomes the "first station" in the token list during token list building. Throughout this document, "token list", "list", "token ring", and "ring" are used synomously unless otherwise indicated.
Another improvement is a more systemitized and less frequent generation of a demand window (see previous '688 application) by providing that the lowest address station (or any other uniquely definable station, if desired) issues an explicit broadcast signal (Demander Enable signal) to all stations to allow any station desiring to be in the ring to reply with a Demander In signal. This Demander In signal is an explicit type signal containing information regarding the station seeking admission to the ring. In particular, since each station has a unique random number associated with its address, the Demander In signal contains not only the address of the demander station but also its random number. This overcomes the possibility of two stations having the same address Demanding In at the same time and both receiving the token from the lowest address station (sometimes called the "window station" herein). Instead, the window station in reply to the Demander In signal sends a Demand Token signal containing not only the address of the station which is perceived as demanding the token but also the random number which is received. Only the station which has the same address and random number can accept the token while the other station with the same address but a different random number realizes that it has a duplicate address with another station, and thereby should take appropriate corrective action.
This use of a random number associated with the station address to prevent stations from being in the ring having the same address is also employed in all of the ring building sequences of the present invention and with respect to all communications generated between stations including those with slave stations.
Furthermore, sine a contentionless system is utilized, a guaranteed maximum access time is obtained by the present communication system. Consequently, the present invention further includes an improvement whereby any station sensing a loss of power can, before all operating power is lost, proceed to patch itself out of the token list and thus achieve an ordered shutdown of itself with respect to the other stations in the token list.
Furthermore, the present invention provides an improvement for the joining of two token lists or two token rings. In particular, each station contains a randomization time associated with its timer. This randomization time prevents stations in the same state to enter the token passing state simultaneously; which in combination with other state transition events, allows only one token from the two token lists to continue, with the stations in the other token list thus able to patch into the existing token list.
Furthermore, the present invention can utilize two communication mediums, such as two coaxial cables, so that a break in any one cable at any one point does not cause a breakdown in the communication network.